The present invention relates to electronic computer architectures and in particular to memory management circuitry providing improved address translation for virtualizing computer systems.
Computer memory system stores electronic representations of data at physical addresses unique and intrinsic to the location of the data. When a program executing on a computer needs to access (read or write) data, it computes and provides to the memory system the physical address of the needed data. The memory uses this physical address to electrically connect to the proper memory location for reading or writing.
Current computer systems may execute multiple programs (processes) using an address translation system which may present to each process a separate, “virtual” memory address space. Each different virtual address space may appear to exist as an identical continuous block of memory and is largely independent of the actual physical memory of the computer. The address translation system (being a combination of specialized hardware and data structures managed by the operating system) positions itself between the executing processes and the physical memory to receive virtual addresses of the virtual address memory space from the processes and to map those virtual addresses to actual physical addresses of the physical memory, the latter which then provides access to the desired data.
This use of virtual memory addresses has several advantages. First, it frees the processes from needing to navigate and manage a shared physical memory space. It also prevents interference between different processes that might overwrite each other's data by segregating each process within a different virtual memory space. Virtual memory addresses also allow the individual processes to execute as if they have more memory than is actually physically available by multiplexing physical memory among multiple virtual address spaces at different times.
The use of virtual memory requires a translation step for each memory access during which a virtual address is translated to a physical address. This translation step can consume substantial memory resources (for holding the translation information) and can slow the speed of execution of a process through the time required to complete the translation.
The amount of memory needed to hold the translation information can be reduced by placing the translation information in a hierarchical page table where initial levels (nodes) of page table receive higher ordered memory addresses and then point to lower levels of page table that decode successively lower orders of memory address. This hierarchy reduces the number of page table entries to less than would otherwise be required if a single entry were recorded for each virtual/physical address translation pair, but at the expense of increasing the number of times that memory needs to be accessed to fully decode a given virtual address. For example, a four-level hierarchical page table would require four separate memory accesses for each virtual memory address translation.
The multiple necessary memory accesses may be greatly reduced by caching recent translation pairs in a “translation lookaside buffer” (TLB). If a translation pair is in the TLB, references to the page table and thus multiple memory accesses can be bypassed.
The concept of virtual memory becomes more complicated under so-called “virtualized” systems in which the processes are managed by multiple “guest” operating systems in turn executed under a “hypervisor or a virtual machine monitor (VMM)”. This use of “virtualization” refers to the fact that each guest operating system appears to operate on a different virtual machine. In virtualization, the guest operating systems may also provide their processes with a virtual address space having a guest of virtual addresses (gVA). Generally, the hypervisor or VMM may be executed natively without the need for a hosting operating system or may be hosted by a hosting operating system. For simplicity, in the context of virtualization, the software implementing the virtualization in either of these cases will be termed a “host operating system” whether it is a hypervisor or VMM alone or a hypervisor or VMM in combination with a hosting operating system.
Using a technique called “nested-paging”, each guest operating system may receive gVA values from its processes and transform them into a guest physical address (gPA) using “guest page tables” in a manner analogous to the translation between virtual and physical addresses performed by a single operating system. The host operating system then translates the gPA addresses into a host physical address (hPA) space using a nested page table. Programs executed natively by the host operating system (including the execution of the guest operating systems) may communicate with physical memory through a single layer of translation using what will be termed “native page tables” translating between the host virtual addresses and the hPA.
Nested-paging used for address translation scales nonlinearly with each layer of virtualization. For example, if four memory accesses are required by the nested page table and four memory accesses are required by the guest page table, twenty-four memory accesses can be required for a two-step translation between gVAs and hPAs. A more detailed example will be provided below.
The number of memory accesses needed in virtualized operating systems may be reduced by combining the guest page table and nested page table into a single “shadow-page table” using a scheme termed “shadow-paging”. The page table of the shadow-page table provide entries that directly map gVAs to hPAs. While shadow-paging reduce the number of memory accesses required for the translation process, they require time-consuming updates to the shadow-pages from the underlying guest page tables and nested page tables when the latter are changed. That is, the shadow-page tables must constantly shadow their counterparts. Normally this updating requires significant processor resources that could otherwise be devoted to the execution of programs and thus can offset some of the benefits of shadow-paging over nested-paging.